Part I Multivariate normal distribution

Let \(\boldsymbol{x} = (x_1, \dots, x_n), n = 100\) be multivariate normal distributed with \(E(x_i) = 0, Var(x_i) = 1\), and \(Corr(x_i, x_j) = e^{-0.1|i - j|}\)

  1. Compute and image the covariance matrix \(\boldsymbol{\Sigma}\) of \(\boldsymbol{x}\)

  2. Find the lower Cholesky factor \(\boldsymbol{L}\), such that \(\boldsymbol{L}\boldsymbol{L}^T = \boldsymbol{\Sigma}\), of this covariance matrix, and image.

  3. Sample \(\boldsymbol{x} = \boldsymbol{Lz}\), where \(\boldsymbol{z}\) is a length n random vector of independent standard normal variables. Plot the sample.

  4. Find the precision matrix \(\boldsymbol{Q}\) of the covariance matrix, and compute the lower Cholesky factor \(\boldsymbol{L}_Q\), such that \(\boldsymbol{L}_Q\boldsymbol{L}_Q^T = \boldsymbol{Q}\), of this matrix. Image these matrices and compare them to the images obtained in a) and b)

  5. Sample \(\boldsymbol{x}\) by solving \(\boldsymbol{L}_Q^T\boldsymbol{x} = \boldsymbol{z}\), where \(\boldsymbol{z}\) is a length n random vector of independen standard normal variables. Plot the sample.

  6. Permute the ordering of variables in \(\boldsymbol{x}\), and redo the exercises.


Solution to Part I

a)

Given that \(\boldsymbol{\Sigma} = e^{-0.1|i - j|}\). The covariance matrix can be expressed as follows: \[\begin{equation*} \Sigma = \begin{pmatrix} 1 & e^{- 0.1 h_{12}} &\dots & e^{- 0.1 h_{1n}} \\ e^{- 0.1 h_{21}} & 1 & \dots & e^{- 0.1 h_{2n}} \\ \vdots & \vdots & \ddots & \vdots \\ e^{- 0.1 h_{n1}} & e^{- 0.1 h_{n2}} & \dots & 1 \end{pmatrix} \end{equation*}\]

### b) According to the cholesky decomposition rule, \(\boldsymbol{L}\) is the lower triangular matrix for \(\boldsymbol{\Sigma}\), it can be easily computed from R using L = chol(Sigma). It is then plotted as below.

c)

Sample using \(\boldsymbol{x} = \boldsymbol{L}\boldsymbol{z}\) transforms the zero-mean, standard normal random variales to the random variables with the desired covariance matrix.

d)

The precision matrix \(\boldsymbol{Q}\) is the inverse of the covariance matrix \(\boldsymbol{\Sigma}\), it is computed using Q = solve(Sigma) in R. The three matrices are thereby depicted as follows. Since the covariance matrix is not singular, given that the it belongs to the Matern family, thus it is analytically guaranteed to have positive definite property. Therefore, both precision matrix and the lower triangular precision matrix exist.

e)

Similarly, the expected random samples can be generated using the inversion of the above formula, thus \(\boldsymbol{L}_Q^T\boldsymbol{x} = \boldsymbol{z}\)

f)

Permute \(\boldsymbol{x}\) to make randomise the ordering of the grid, the asscociated covariance matrix can be thereby modified in a sparse way.

Part II Gaussian random fields and Kriging

The purpose of this computer exercise is to give an introduction to parameter estima- tion and kriging for Gaussian random field models for spatial data.

We assume the following observation model on the unit square:

\[\begin{equation*} y(\boldsymbol{s}_j) = x(\boldsymbol{s}_j) + \epsilon_j, \ \ \ j = 1, \dots, N, \end{equation*}\]

where \(\epsilon_j ~ \mathop{N}(0, \tau^2)\) are independent measurement noise terms. Further, consider a Matérn covariance function for the Gaussian random field \(\boldsymbol{x(s)}\):

\[\begin{equation*} Cov(x(\boldsymbol{s}_i), x(\boldsymbol{s}_j)) = \Sigma_{i, j} = \sigma^2(1 + \phi h)\exp(-\phi h), \end{equation*}\]

where \(h\) denotes the Euclidean distance between the two sites \(\boldsymbol{s}_i\) and \(\boldsymbol{s}_j\).

We assume the mean increases with east and north coordinates as follows: \(\mu_j = \alpha((s_{j1} - 0.5) + (s_{j2} - 0.5))\), for site \(\boldsymbol{s}_j = (s_{j1}, s_{j2})\) on the unit square.


2.1 Simulation

Simulate \(N = 200\) random sites in the unit square and plot them. Form the covariance matrix using \(\sigma = 1, \phi = 10, \tau = 0.05\). Take its Cholesky decomposition and simulate dependent zero-mean Gaussian data variables, then add the mean using \(\alpha = 1\). Plot your observations.


2.2 Paramter estimation

We will now use the simulated data to estimate the model parameters \(\alpha, \sigma^2, \tau^2, \phi\) using maximum likelihood estimation. Iterate between the update for the mean parameter, and updating the covariance parameters. Monitor the likelihood function at each step of the algorithm to check convergence.

## [1] "0.895765013504915  , iter no is  0"
## [1] "0.304910507162466  , iter no is  1"
## [1] "0.270287466981051  , iter no is  2"
## [1] "0.222351840261664  , iter no is  3"
## [1] "0.202516701628354  , iter no is  4"

## 
## Estimated sigma is  1.125 ; True sigma is  1 
## Estimated phi is  10.54 ; True phi is  10 
## Estimated tau is  0.01016 ; True tau is  0.05 
## Estimated beta1 is  -0.93 ; True beta1 is  -1 
## Estimated beta2 is  1.34 ; True beta2 is  1 
## Estimated beta3 is  0.92 ; True beta3 is  1NULL

2.3 Kriging

We will now use the estimated model parameters to perform kriging prediction. Predict variables \(x(s)\), where predictions sites lie on a regular grid of size 25x25 for the unit square. Visualize the Kriging surface and the prediction standard error. Compare with the true field.

## [1] "The prediction error is  1.93020697440398"

Part III

LS0tCnRpdGxlOiAiUHJvamVjdDIiCnN1YnRpdGxlOiAiR2F1c3NpYW4gcmFuZG9tIGZpZWxkIHdpdGggYXBwbGljYXRpb24gb2YgSU5MQSIKYXV0aG9yOiAkXG92ZXJzZXR7XG1hdGhybXt5YW9saW4uZ2VAbnRudS5ub319ezEwMDI2fSQgXGFuZAogICAgICAgICRcb3ZlcnNldHtcbWF0aHJte3lhb2xpbi5nZUBudG51Lm5vfX17MTAwMjZ9JApvdXRwdXQ6CiAgIyBwZGZfZG9jdW1lbnQ6CiAgIyAgIHRvYzogdHJ1ZQogICMgICB0b2NfZGVwdGg6IDMKICAjICAgbnVtYmVyX3NlY3Rpb25zOiB0cnVlCiAgaHRtbF9kb2N1bWVudDoKICAgIHRvYzogeWVzCiAgICB0b2NfZmxvYXQ6IHllcwogICAgY29kZV9kb3dubG9hZDogeWVzCiAgICB0b2NfZGVwdGg6IDMKICBpb3NsaWRlc19wcmVzZW50YXRpb246IGRlZmF1bHQKICBiZWFtZXJfcHJlc2VudGF0aW9uOgogICAgc2xpZGVfbGV2ZWw6IDEKICAgIGtlZXBfdGV4OiB5ZXMKICBwZGZfZG9jdW1lbnQ6CiAgICB0b2M6IHllcwogICAgdG9jX2RlcHRoOiAyCi0tLQoKYGBge3Igc2V0dXAsIGluY2x1ZGU9VFJVRSxlY2hvPUZBTFNFfQpzdXBwcmVzc1BhY2thZ2VTdGFydHVwTWVzc2FnZXMobGlicmFyeShrbml0cikpCmtuaXRyOjpvcHRzX2NodW5rJHNldChlY2hvID0gRkFMU0UsIG1lc3NhZ2U9RkFMU0Usd2FybmluZyA9IEZBTFNFLCBlcnJvciA9IEZBTFNFKQpgYGAKCmBgYHtyIGxvYWQgbGlicmFyaWVzLCBlY2hvID0gRn0KbGlicmFyeShsYXR0aWNlKQpsaWJyYXJ5KHZpcmlkaXNMaXRlKQpjb3VsIDwtIHZpcmlkaXMoMTAwKQpgYGAKCiMgUGFydCBJIE11bHRpdmFyaWF0ZSBub3JtYWwgZGlzdHJpYnV0aW9uCkxldCAkXGJvbGRzeW1ib2x7eH0gPSAoeF8xLCBcZG90cywgeF9uKSwgbiA9IDEwMCQgYmUgbXVsdGl2YXJpYXRlIG5vcm1hbCBkaXN0cmlidXRlZCB3aXRoICRFKHhfaSkgPSAwLCBWYXIoeF9pKSA9IDEkLCBhbmQgJENvcnIoeF9pLCB4X2opID0gZV57LTAuMXxpIC0ganx9JAoKYSkgQ29tcHV0ZSBhbmQgaW1hZ2UgdGhlIGNvdmFyaWFuY2UgbWF0cml4ICRcYm9sZHN5bWJvbHtcU2lnbWF9JCBvZiAkXGJvbGRzeW1ib2x7eH0kCgpiKSBGaW5kIHRoZSBsb3dlciBDaG9sZXNreSBmYWN0b3IgJFxib2xkc3ltYm9se0x9JCwgc3VjaCB0aGF0ICRcYm9sZHN5bWJvbHtMfVxib2xkc3ltYm9se0x9XlQgPSBcYm9sZHN5bWJvbHtcU2lnbWF9JCwgb2YgdGhpcyBjb3ZhcmlhbmNlIG1hdHJpeCwgYW5kIGltYWdlLgoKYykgU2FtcGxlICRcYm9sZHN5bWJvbHt4fSA9IFxib2xkc3ltYm9se0x6fSQsIHdoZXJlICRcYm9sZHN5bWJvbHt6fSQgaXMgYSBsZW5ndGggbiByYW5kb20gdmVjdG9yIG9mIGluZGVwZW5kZW50IHN0YW5kYXJkIG5vcm1hbCB2YXJpYWJsZXMuIFBsb3QgdGhlIHNhbXBsZS4KCmQpIEZpbmQgdGhlIHByZWNpc2lvbiBtYXRyaXggJFxib2xkc3ltYm9se1F9JCBvZiB0aGUgY292YXJpYW5jZSBtYXRyaXgsIGFuZCBjb21wdXRlIHRoZSBsb3dlciBDaG9sZXNreSBmYWN0b3IgJFxib2xkc3ltYm9se0x9X1EkLCBzdWNoIHRoYXQgJFxib2xkc3ltYm9se0x9X1FcYm9sZHN5bWJvbHtMfV9RXlQgPSBcYm9sZHN5bWJvbHtRfSQsIG9mIHRoaXMgbWF0cml4LiBJbWFnZSB0aGVzZSBtYXRyaWNlcyBhbmQgY29tcGFyZSB0aGVtIHRvIHRoZSBpbWFnZXMgb2J0YWluZWQgaW4gYSkgYW5kIGIpCgplKSBTYW1wbGUgJFxib2xkc3ltYm9se3h9JCBieSBzb2x2aW5nICRcYm9sZHN5bWJvbHtMfV9RXlRcYm9sZHN5bWJvbHt4fSA9IFxib2xkc3ltYm9se3p9JCwgd2hlcmUgJFxib2xkc3ltYm9se3p9JCBpcyBhIGxlbmd0aCBuIHJhbmRvbSB2ZWN0b3Igb2YgaW5kZXBlbmRlbiBzdGFuZGFyZCBub3JtYWwgdmFyaWFibGVzLiBQbG90IHRoZSBzYW1wbGUuCgpmKSBQZXJtdXRlIHRoZSBvcmRlcmluZyBvZiB2YXJpYWJsZXMgaW4gJFxib2xkc3ltYm9se3h9JCwgYW5kIHJlZG8gdGhlIGV4ZXJjaXNlcy4gCgoKKioqCgojIyBTb2x1dGlvbiB0byBQYXJ0IEkKCiMjIyBhKSAKR2l2ZW4gdGhhdCAkXGJvbGRzeW1ib2x7XFNpZ21hfSA9IGVeey0wLjF8aSAtIGp8fSQuIFRoZSBjb3ZhcmlhbmNlIG1hdHJpeCBjYW4gYmUgZXhwcmVzc2VkIGFzIGZvbGxvd3M6ClxiZWdpbntlcXVhdGlvbip9CiAgICBcU2lnbWEgPSBcYmVnaW57cG1hdHJpeH0gCiAgICAxICYgIGVeey0gMC4xIGhfezEyfX0gJlxkb3RzICYgZV57LSAwLjEgaF97MW59fSBcXAogICAgZV57LSAwLjEgaF97MjF9fSAmIDEgJiBcZG90cyAmIGVeey0gMC4xIGhfezJufX0gXFwKICAgIFx2ZG90cyAmIFx2ZG90cyAmIFxkZG90cyAmIFx2ZG90cyBcXAogICAgZV57LSAwLjEgaF97bjF9fSAmIGVeey0gMC4xIGhfe24yfX0gJiBcZG90cyAmIDEKICAgIFxlbmR7cG1hdHJpeH0KXGVuZHtlcXVhdGlvbip9CgpgYGB7ciBjb3ZhcmlhbmNlIG1hdHJpeCwgZWNobyA9IEYsIGZpZy5hbGlnbj0nY2VudGVyJ30KIyBzaXplcwpuIDwtIDEwMAoKIyBkZWZpbmUgcmVndWxhciBncmlkIG9mIGxvY2F0aW9ucwpzaXRlczF2IDwtIGFycmF5KCgxOm4pLGMobiwxKSkKCiMgUHJpb3IgbWVhbgptIDwtIDAKIyBjb21wdXRlIEVhc3QgYW5kIE5vcnRoIGRpc3RhbmNlcyBvbiBncmlkCnd3IDwtIGFycmF5KDEsYyhuLDEpKQoKIyBkZXRlcm1pbmUgdGhlIGRpc3RhbmNlIG1hdHJpeApIIDwtIGFicyhzaXRlczF2JSoldCh3dyktd3cgJSolIHQoc2l0ZXMxdikpCgojIEV4cG9uZW50aWFsIGNvdmFyaWFuY2UgbW9kZWwKU2lnbWEgPC0gZXhwKC0wLjEqSCkKCiMgUGxvdCB0aGUgY292YXJpYW5jZSBtYXRyaXgKbGV2ZWxwbG90KFNpZ21hLCBjb2wucmVnaW9ucyA9IGNvdWwsIG1haW4gPSAiQ292YXJpYW5jZSBtYXRyaXgiKQpgYGAKIyMjIGIpIApBY2NvcmRpbmcgdG8gdGhlIGNob2xlc2t5IGRlY29tcG9zaXRpb24gcnVsZSwgJFxib2xkc3ltYm9se0x9JCBpcyB0aGUgbG93ZXIgdHJpYW5ndWxhciBtYXRyaXggZm9yICRcYm9sZHN5bWJvbHtcU2lnbWF9JCwgaXQgY2FuIGJlIGVhc2lseSBjb21wdXRlZCBmcm9tIFIgdXNpbmcgYEwgPSBjaG9sKFNpZ21hKWAuIEl0IGlzIHRoZW4gcGxvdHRlZCBhcyBiZWxvdy4gCgpgYGB7ciBDaG9sZXNreSwgZWNobyA9IEYsIGZpZy5hbGlnbj0nY2VudGVyJ30KTCA8LSBjaG9sKFNpZ21hKQpsZXZlbHBsb3QoTCwgY29sLnJlZ2lvbnMgPSBjb3VsLCBtYWluID0gIkxvd2VyIHRyaWFuZ3VsYXIgbWF0cml4IikKYGBgCgoKIyMjIGMpIApTYW1wbGUgdXNpbmcgJFxib2xkc3ltYm9se3h9ID0gXGJvbGRzeW1ib2x7TH1cYm9sZHN5bWJvbHt6fSQgdHJhbnNmb3JtcyB0aGUgemVyby1tZWFuLCBzdGFuZGFyZCBub3JtYWwgcmFuZG9tIHZhcmlhbGVzIHRvIHRoZSByYW5kb20gdmFyaWFibGVzIHdpdGggdGhlIGRlc2lyZWQgY292YXJpYW5jZSBtYXRyaXguIAoKYGBge3IsIHJhbmRvbSBzYW1wbGVzLCBmaWcuYWxpZ249J2NlbnRlcid9CnogPSBybm9ybSgxMDApCnggPSBMICUqJSB6CnBsb3QoeCwgbWFpbiA9ICJSYW5kb20gc2FtcGxlcyBnaXZlbiB0aGUgY292YXJpYW5jZSIpCmBgYAoKCiMjIyBkKSAKVGhlIHByZWNpc2lvbiBtYXRyaXggJFxib2xkc3ltYm9se1F9JCBpcyB0aGUgaW52ZXJzZSBvZiB0aGUgY292YXJpYW5jZSBtYXRyaXggJFxib2xkc3ltYm9se1xTaWdtYX0kLCBpdCBpcyBjb21wdXRlZCB1c2luZyBgUSA9IHNvbHZlKFNpZ21hKWAgaW4gUi4gVGhlIHRocmVlIG1hdHJpY2VzIGFyZSB0aGVyZWJ5IGRlcGljdGVkIGFzIGZvbGxvd3MuIFNpbmNlIHRoZSBjb3ZhcmlhbmNlIG1hdHJpeCBpcyBub3Qgc2luZ3VsYXIsIGdpdmVuIHRoYXQgdGhlIGl0IGJlbG9uZ3MgdG8gdGhlIE1hdGVybiBmYW1pbHksIHRodXMgaXQgaXMgYW5hbHl0aWNhbGx5IGd1YXJhbnRlZWQgdG8gaGF2ZSBwb3NpdGl2ZSBkZWZpbml0ZSBwcm9wZXJ0eS4gVGhlcmVmb3JlLCBib3RoIHByZWNpc2lvbiBtYXRyaXggYW5kIHRoZSBsb3dlciB0cmlhbmd1bGFyIHByZWNpc2lvbiBtYXRyaXggZXhpc3QuIAoKYGBge3IgY29tcCBiZXR3ZWVuIHRocmVlIG1hdHJpY2VzLCBmaWcuc2hvdyA9ICJob2xkIiwgb3V0LndpZHRoPSI1MCUifQpRIDwtIHNvbHZlKFNpZ21hKQpMUSA8LSBjaG9sKFEpCnBhcihtYXIgPSBjKDQsNCwuMSwgLjEpKQojIHBhcihtZnJvdz1jKDEsMyksIG1hcj1jKDQsNCw0LDEpLCBvbWE9YygwLjUsMC41LDAuNSwwKSkKbGV2ZWxwbG90KFNpZ21hLCBjb2wucmVnaW9ucyA9IGNvdWwsIG1haW4gPSAiQ292YXJpYW5jZSBtYXRyaXgiKQpsZXZlbHBsb3QoTCwgY29sLnJlZ2lvbnMgPSBjb3VsLCBtYWluID0gIkxvd2VyIHRyaWFuZ3VsYXIgY292YXJpYW5jZSBtYXRyaXgiKQpsZXZlbHBsb3QoUSwgY29sLnJlZ2lvbnMgPSBjb3VsLCBtYWluID0gIlByZWNpc2lvbiBtYXRyaXgiKQpsZXZlbHBsb3QoTFEsIGNvbC5yZWdpb25zID0gY291bCwgbWFpbiA9ICJMb3dlciB0cmlhbmd1bGFyIHByZWNpc2lvbiBtYXRyaXgiKQojIGxldmVscGxvdChMUSwgY29sLnJlZ2lvbnMgPSBjb3VsLCBtYWluID0gIkxvd2VyIHRyaWFuZ3VsYXIgbWF0cml4IikKYGBgCgoKIyMjIGUpIApTaW1pbGFybHksIHRoZSBleHBlY3RlZCByYW5kb20gc2FtcGxlcyBjYW4gYmUgZ2VuZXJhdGVkIHVzaW5nIHRoZSBpbnZlcnNpb24gb2YgdGhlIGFib3ZlIGZvcm11bGEsIHRodXMgJFxib2xkc3ltYm9se0x9X1FeVFxib2xkc3ltYm9se3h9ID0gXGJvbGRzeW1ib2x7en0kCgpgYGB7ciwgc2FtcGxlIGluIGludmVyc2lvbiB3YXksIGZpZy5hbGlnbj0nY2VudGVyJ30KeiA9IHJub3JtKDEwMCkKeCA9IHNvbHZlKHQoTFEpLCB6KQpwbG90KHgsIG1haW4gPSAiUmFuZG9tIHNhbXBsZXMgdXNpbmcgaW52ZXJzaW9uIHJ1bGUiKQpgYGAKCiMjIyBmKSAKUGVybXV0ZSAkXGJvbGRzeW1ib2x7eH0kIHRvIG1ha2UgcmFuZG9taXNlIHRoZSBvcmRlcmluZyBvZiB0aGUgZ3JpZCwgdGhlIGFzc2NvY2lhdGVkIGNvdmFyaWFuY2UgbWF0cml4IGNhbiBiZSB0aGVyZWJ5IG1vZGlmaWVkIGluIGEgc3BhcnNlIHdheS4gCgpgYGB7ciwgcGVybXV0YXRpb24sIGZpZy5hbGlnbj0nY2VudGVyJ30Kbl9wZXIgPSAzClNpZ21hX3BlciA8LSBsaXN0KCkKTF9wZXIgPC0gbGlzdCgpClFfcGVyIDwtIGxpc3QoKQpMUV9wZXIgPC0gbGlzdCgpCmZvciAoaSBpbiBjKDE6bl9wZXIpKXsKICBzaXRlczF2X3BlciA8LSBhcnJheShzYW1wbGUoc2l0ZXMxdiwgc2l6ZSA9IG4sIHJlcGxhY2UgPSBGQUxTRSksIGMobiwxKSkKICAjIGRldGVybWluZSB0aGUgZGlzdGFuY2UgbWF0cml4CiAgSF9wZXIgPC0gYWJzKHNpdGVzMXZfcGVyJSoldCh3dyktd3cgJSolIHQoc2l0ZXMxdl9wZXIpKQogICMgRXhwb25lbnRpYWwgY292YXJpYW5jZSBtb2RlbAogIFNpZ21hX3RlbXAgPC0gZXhwKC0wLjEqSF9wZXIpCiAgU2lnbWFfcGVyW1tpXV0gPC0gU2lnbWFfdGVtcAogICMgTCBtYXRyaXgKICBMX3RlbXAgPC0gY2hvbChTaWdtYV90ZW1wKQogIExfcGVyW1tpXV0gPC0gTF90ZW1wCiAgCiAgeiA9IHJub3JtKDEwMCkKICB4X3BlciA9IExfdGVtcCAlKiUgegogIHBsb3QoeF9wZXIsIG1haW4gPSBwYXN0ZShpLCAiUGVybXV0ZWQgcmFuZG9tIHNhbXBsZXMgZ2l2ZW4gdGhlIGNvdmFyaWFuY2UiKSkKICAKICBRX3RlbXAgPC0gc29sdmUoU2lnbWFfdGVtcCkKICBMUV90ZW1wIDwtIGNob2woUV90ZW1wKQogIFFfcGVyW1tpXV0gPC0gUV90ZW1wCiAgTFFfcGVyW1tpXV0gPC0gTFFfdGVtcAogIHogPSBybm9ybSgxMDApCiAgeF9wZXIgPSBzb2x2ZSh0KExRX3RlbXApLCB6KQogIHBsb3QoeF9wZXIsIG1haW4gPSBwYXN0ZShpLCAiUGVybXV0ZWQgcmFuZG9tIHNhbXBsZXMgdXNpbmcgaW52ZXJzaW9uIHJ1bGUiKSkKfQoKCmBgYAoKYGBge3IsIGNvbnQgcGxvdHRpbmcgMSwgZmlnLnNob3cgPSAiaG9sZCIsIG91dC53aWR0aD0iNTAlIn0KaSA9IDEKcGFyKG1hciA9IGMoNCwgNCwuMSwgLjEpKQojIHBhcihtZnJvdz1jKDEsMyksIG1hcj1jKDQsNCw0LDEpLCBvbWE9YygwLjUsMC41LDAuNSwwKSkKbGV2ZWxwbG90KFNpZ21hX3BlcltbaV1dLCBjb2wucmVnaW9ucyA9IGNvdWwsIG1haW4gPSBwYXN0ZShpLCAiUGVybXV0ZWQgY292YXJpYW5jZSBtYXRyaXgiKSkKbGV2ZWxwbG90KExfcGVyW1tpXV0sIGNvbC5yZWdpb25zID0gY291bCwgbWFpbiA9IHBhc3RlKGksIlBlcm11dGVkIGxvd2VyIHRyaWFuZ3VsYXIgY292YXJpYW5jZSBtYXRyaXgiKSkKbGV2ZWxwbG90KFFfcGVyW1tpXV0sIGNvbC5yZWdpb25zID0gY291bCwgbWFpbiA9IHBhc3RlKGksIlBlcm11dGVkIHByZWNpc2lvbiBtYXRyaXgiKSkKbGV2ZWxwbG90KExRX3BlcltbaV1dLCBjb2wucmVnaW9ucyA9IGNvdWwsIG1haW4gPSBwYXN0ZShpLCJQZXJtdXRlZCBsb3dlciB0cmlhbmd1bGFyIHByZWNpc2lvbiBtYXRyaXgiKSkKYGBgCgpgYGB7ciwgY29udCBwbG90dGluZyAyLCBmaWcuc2hvdyA9ICJob2xkIiwgb3V0LndpZHRoPSI1MCUifQppID0gMgpwYXIobWFyID0gYyg0LCA0LC4xLCAuMSkpCiMgcGFyKG1mcm93PWMoMSwzKSwgbWFyPWMoNCw0LDQsMSksIG9tYT1jKDAuNSwwLjUsMC41LDApKQpsZXZlbHBsb3QoU2lnbWFfcGVyW1tpXV0sIGNvbC5yZWdpb25zID0gY291bCwgbWFpbiA9IHBhc3RlKGksICJQZXJtdXRlZCBjb3ZhcmlhbmNlIG1hdHJpeCIpKQpsZXZlbHBsb3QoTF9wZXJbW2ldXSwgY29sLnJlZ2lvbnMgPSBjb3VsLCBtYWluID0gcGFzdGUoaSwiUGVybXV0ZWQgbG93ZXIgdHJpYW5ndWxhciBjb3ZhcmlhbmNlIG1hdHJpeCIpKQpsZXZlbHBsb3QoUV9wZXJbW2ldXSwgY29sLnJlZ2lvbnMgPSBjb3VsLCBtYWluID0gcGFzdGUoaSwiUGVybXV0ZWQgcHJlY2lzaW9uIG1hdHJpeCIpKQpsZXZlbHBsb3QoTFFfcGVyW1tpXV0sIGNvbC5yZWdpb25zID0gY291bCwgbWFpbiA9IHBhc3RlKGksIlBlcm11dGVkIGxvd2VyIHRyaWFuZ3VsYXIgcHJlY2lzaW9uIG1hdHJpeCIpKQpgYGAKCmBgYHtyLCBjb250IHBsb3R0aW5nIDMsIGZpZy5zaG93ID0gImhvbGQiLCBvdXQud2lkdGg9IjUwJSJ9CmkgPSAzCnBhcihtYXIgPSBjKDQsIDQsLjEsIC4xKSkKIyBwYXIobWZyb3c9YygxLDMpLCBtYXI9Yyg0LDQsNCwxKSwgb21hPWMoMC41LDAuNSwwLjUsMCkpCmxldmVscGxvdChTaWdtYV9wZXJbW2ldXSwgY29sLnJlZ2lvbnMgPSBjb3VsLCBtYWluID0gcGFzdGUoaSwgIlBlcm11dGVkIGNvdmFyaWFuY2UgbWF0cml4IikpCmxldmVscGxvdChMX3BlcltbaV1dLCBjb2wucmVnaW9ucyA9IGNvdWwsIG1haW4gPSBwYXN0ZShpLCJQZXJtdXRlZCBsb3dlciB0cmlhbmd1bGFyIGNvdmFyaWFuY2UgbWF0cml4IikpCmxldmVscGxvdChRX3BlcltbaV1dLCBjb2wucmVnaW9ucyA9IGNvdWwsIG1haW4gPSBwYXN0ZShpLCJQZXJtdXRlZCBwcmVjaXNpb24gbWF0cml4IikpCmxldmVscGxvdChMUV9wZXJbW2ldXSwgY29sLnJlZ2lvbnMgPSBjb3VsLCBtYWluID0gcGFzdGUoaSwiUGVybXV0ZWQgbG93ZXIgdHJpYW5ndWxhciBwcmVjaXNpb24gbWF0cml4IikpCmBgYAoKCgojIFBhcnQgSUkgR2F1c3NpYW4gcmFuZG9tIGZpZWxkcyBhbmQgS3JpZ2luZwoKVGhlIHB1cnBvc2Ugb2YgdGhpcyBjb21wdXRlciBleGVyY2lzZSBpcyB0byBnaXZlIGFuIGludHJvZHVjdGlvbiB0byBwYXJhbWV0ZXIgZXN0aW1hLSB0aW9uIGFuZCBrcmlnaW5nIGZvciBHYXVzc2lhbiByYW5kb20gZmllbGQgbW9kZWxzIGZvciBzcGF0aWFsIGRhdGEuCgpXZSBhc3N1bWUgdGhlIGZvbGxvd2luZyBvYnNlcnZhdGlvbiBtb2RlbCBvbiB0aGUgdW5pdCBzcXVhcmU6CgpcYmVnaW57ZXF1YXRpb24qfQogICAgeShcYm9sZHN5bWJvbHtzfV9qKSA9IHgoXGJvbGRzeW1ib2x7c31faikgKyBcZXBzaWxvbl9qLCBcIFwgXCAgaiA9IDEsIFxkb3RzLCBOLApcZW5ke2VxdWF0aW9uKn0KCndoZXJlICRcZXBzaWxvbl9qIH4gXG1hdGhvcHtOfSgwLCBcdGF1XjIpJCBhcmUgaW5kZXBlbmRlbnQgbWVhc3VyZW1lbnQgbm9pc2UgdGVybXMuIEZ1cnRoZXIsIGNvbnNpZGVyIGEgTWF0w6lybiBjb3ZhcmlhbmNlIGZ1bmN0aW9uIGZvciB0aGUgR2F1c3NpYW4gcmFuZG9tIGZpZWxkICRcYm9sZHN5bWJvbHt4KHMpfSQ6CgpcYmVnaW57ZXF1YXRpb24qfQogICAgQ292KHgoXGJvbGRzeW1ib2x7c31faSksIHgoXGJvbGRzeW1ib2x7c31faikpID0gXFNpZ21hX3tpLCBqfSA9IFxzaWdtYV4yKDEgKyBccGhpIGgpXGV4cCgtXHBoaSBoKSwKXGVuZHtlcXVhdGlvbip9Cgp3aGVyZSAkaCQgZGVub3RlcyB0aGUgRXVjbGlkZWFuIGRpc3RhbmNlIGJldHdlZW4gdGhlIHR3byBzaXRlcyAkXGJvbGRzeW1ib2x7c31faSQgYW5kICRcYm9sZHN5bWJvbHtzfV9qJC4KCldlIGFzc3VtZSB0aGUgbWVhbiBpbmNyZWFzZXMgd2l0aCBlYXN0IGFuZCBub3J0aCBjb29yZGluYXRlcyBhcyBmb2xsb3dzOiAkXG11X2ogPSBcYWxwaGEoKHNfe2oxfSAtIDAuNSkgKyAoc197ajJ9IC0gMC41KSkkLCBmb3Igc2l0ZSAkXGJvbGRzeW1ib2x7c31faiA9IChzX3tqMX0sIHNfe2oyfSkkIG9uIHRoZSB1bml0IHNxdWFyZS4gCgoqKiogCgojIyAyLjEgU2ltdWxhdGlvbgoKU2ltdWxhdGUgJE4gPSAyMDAkIHJhbmRvbSBzaXRlcyBpbiB0aGUgdW5pdCBzcXVhcmUgYW5kIHBsb3QgdGhlbS4gRm9ybSB0aGUgY292YXJpYW5jZSBtYXRyaXggdXNpbmcgJFxzaWdtYSA9IDEsIFxwaGkgPSAxMCwgXHRhdSA9IDAuMDUkLiBUYWtlIGl0cyBDaG9sZXNreSBkZWNvbXBvc2l0aW9uIGFuZCBzaW11bGF0ZSBkZXBlbmRlbnQgemVyby1tZWFuIEdhdXNzaWFuIGRhdGEgdmFyaWFibGVzLCB0aGVuIGFkZCB0aGUgbWVhbiB1c2luZyAkXGFscGhhID0gMSQuIFBsb3QgeW91ciBvYnNlcnZhdGlvbnMuCgpgYGB7ciBHUCBzaW11bGF0aW9ufQoKTWF0ZXJuX2NvdiA8LSBmdW5jdGlvbihzaWdtYSwgcGhpLCB0KXsKICAgICMgcGFyYW0gc2lnbWE6IHNjYWxpbmcgY29lZgogICAgIyBwYXJhbSBldGE6IHJhbmdlIGNvZWYKICAgICMgcGFyYW0gdDogZGlzdGFuY2UgbWF0cml4CiAgICAjIHJldHVybjogbWF0ZXJuIGNvdmFyaWFuY2UKICAgIHJldHVybihzaWdtYSBeIDIgKiAoMSArIHBoaSAqIHQpICogZXhwKC1waGkgKiB0KSkKfQoKcGxvdGYgPC0gZnVuY3Rpb24odiwgc3RyaW5nKXsKICB2diA8LSB2CiAgZGltKHZ2KSA8LSBjKG4xLCBuMikKICBsZXZlbHBsb3QodnYsIGNvbC5yZWdpb25zID0gY291bCwgbWFpbiA9IHN0cmluZykKfQoKIyBTZXR1cCB0aGUgZ3JpZApuMSA9IDI1ICMgbnVtYmVyIG9mIGdyaWQgcG9pbnRzIGFsb25nIGVhc3QgZGlyZWN0aW9uCm4yID0gMjUgIyBudW1iZXIgb2YgZ3JpZCBwb2ludHMgYWxvbmcgbm9ydGggZGlyZWN0aW9uCm4gPSBuMSAqIG4yICMgdG90YWwgbnVtYmVyIG9mIGdyaWQgcG9pbnRzCgpkbjEgPSAxL24xCmRuMiA9IDEvbjIKc2l0ZXMxID0gYXJyYXkoc2VxKDAsIDEsIGRuMSksIGMobjEsIDEpKQpzaXRlczIgPSBhcnJheShzZXEoMCwgMSwgZG4yKSwgYyhuMiwgMSkpCiMgc2l0ZXMxID0gYXJyYXkoc2VxKDEsIG4xKSwgYyhuMSwgMSkpCiMgc2l0ZXMyID0gYXJyYXkoc2VxKDEsIG4yKSwgYyhuMiwgMSkpCnd3MSA9IHJlcCgxLCBuMSkKd3cyID0gcmVwKDEsIG4yKQpzaXRlczFtID0gc2l0ZXMxICUqJSB0KHd3MSkgIyBzaXRlczFtIGlzIHRoZSBtYXRyaXggdmVyc2lvbiBvZiBzaXRlczEKc2l0ZXMybSA9IHd3MiAlKiUgdChzaXRlczIpCgpzaXRlczF2ID0gbWF0cml4KHNpdGVzMW0sIG5yb3cgPSBuLCBuY29sID0gMSkKc2l0ZXMydiA9IG1hdHJpeChzaXRlczJtLCBucm93ID0gbiwgbmNvbCA9IDEpCgpwbG90KHNpdGVzMXYsIHNpdGVzMnYpCgojIENvbXB1dGUgdGhlIGRpc3RhbmNlIG1hdHJpeApkZEUgPSBzaXRlczF2ICUqJSBtYXRyaXgocmVwKDEsIG4pLCBucm93ID0gMSwgbmNvbCA9IG4pIC0gbWF0cml4KHJlcCgxLCBuKSwgbnJvdyA9IG4sIG5jb2wgPSAxKSAlKiUgdChzaXRlczF2KQpkZDJFID0gZGRFICogZGRFCmRkTiA9IHNpdGVzMnYgJSolIG1hdHJpeChyZXAoMSwgbiksIG5yb3cgPSAxLCBuY29sID0gbikgLSBtYXRyaXgocmVwKDEsIG4pLCBucm93ID0gbiwgbmNvbCA9IDEpICUqJSB0KHNpdGVzMnYpCmRkMk4gPSBkZE4gKiBkZE4KdCA9IHNxcnQoZGQyRSArIGRkMk4pCmxldmVscGxvdCh0LCBjb2wucmVnaW9ucyA9IGNvdWwsIG1haW4gPSAiRGlzdGFuY2UgbWF0cml4IikKCiMgU2ltdWxhdGUgdGhlIGluaXRpYWwgcmFuZG9tIGZpZWxkCmFscGhhID0gMS4wICMgYmV0YSBhcyBpbiByZWdyZXNzaW9uIG1vZGVsCnNpZ21hID0gMS4wICAjIHNjYWxpbmcgY29lZiBpbiBtYXRlcm4ga2VybmVsCnBoaSA9IDEwICMgcmFuZ2UgY29lZiBpbiBtYXRlcm4ga2VybmVsCiMgZXRhID0gMTAgIyByYW5nZSBjb2VmIGluIG1hdGVybiBrZXJuZWwKdGF1ID0gLjA1ICMgaWlkIG5vaXNlCgpiZXRhMSA9IC1hbHBoYQpiZXRhMiA9IGFscGhhCmJldGEzID0gYWxwaGEKCkJFVEFfVFJVRSA9IG1hdHJpeChjKGJldGExLCBiZXRhMiwgYmV0YTMpLCBucm93ID0gMywgbmNvbCA9IDEpClRIRVRBX1RSVUUgPSBtYXRyaXgoYyhzaWdtYSwgcGhpLCB0YXUpLCBucm93ID0gMywgbmNvbCA9IDEpCgpTaWdtYSA9IE1hdGVybl9jb3Yoc2lnbWEsIHBoaSwgdCkgICMgbWF0ZXJuIGNvdmFyaWFuY2UKCkwgPSBjaG9sKFNpZ21hKSAjIGxvd2VyIEwKeCA9IHQoTCkgJSolIHJub3JtKG4pICMgc2FtcGxlIGZyb20gemVybyBtZWFuIHJhbmRvbSB2YXJpYWJsZXMKCkggPSBhcnJheShjKHJlcCgxLCBuKSwgc2l0ZXMxdiwgc2l0ZXMydiksIGRpbSA9IGMobiwgMykpICMgZGVzaWduIG1hdHJpeAptdV9wcmlvciA9IEggJSolIEJFVEFfVFJVRQpwbG90ZihtdV9wcmlvciwgInByaW9yIG1lYW4iKQptdV9yZWFsID0gbXVfcHJpb3IgKyB4CnBsb3RmKG11X3JlYWwsICJyZWFsaXNhdGlvbiBvZiB0aGUgZ3JmIikKCiMgc2FtcGxpbmcgZnJvbSByZWFsaXNhdGlvbnMKTSA9IDIwMApGbWF0cml4ID0gbWF0cml4KDAsIE0sIG4pCmluZCA9IHNhbXBsZShuLCBzaXplID0gTSwgcmVwbGFjZSA9IEZBTFNFKQpmb3IgKGkgaW4gYygxOk0pKXsKICBGbWF0cml4W2ksIGluZFtpXV0gPSBUUlVFCn0KRyA9IEZtYXRyaXggJSolIEgKeV9zYW1wbGVkID0gRm1hdHJpeCAlKiUgbXVfcmVhbCArIHRhdSAqIHJub3JtKE0sIDEpCnhfaW5kID0gc2l0ZXMxdltpbmRdCnlfaW5kID0gc2l0ZXMydltpbmRdCgpwbG90KHhfaW5kLCB5X2luZCwgY2V4ID0gYWJzKHlfc2FtcGxlZCksIG1haW4gPSAiUmFuZG9tIHNhbXBsZXMgaW4gdGhlIGZpZWxkLCBjaXJjbGUgc2l6ZSBpbmRpY2F0ZXMgdGhlIHJlbGF0aXZlIHZhbHVlIikKCmBgYAoKKioqCgojIyAyLjIgUGFyYW10ZXIgZXN0aW1hdGlvbgoKV2Ugd2lsbCBub3cgdXNlIHRoZSBzaW11bGF0ZWQgZGF0YSB0byBlc3RpbWF0ZSB0aGUgbW9kZWwgcGFyYW1ldGVycyAkXGFscGhhLCBcc2lnbWFeMiwgXHRhdV4yLCBccGhpJCB1c2luZyBtYXhpbXVtIGxpa2VsaWhvb2QgZXN0aW1hdGlvbi4gSXRlcmF0ZSBiZXR3ZWVuIHRoZSB1cGRhdGUgZm9yIHRoZSBtZWFuIHBhcmFtZXRlciwgYW5kIHVwZGF0aW5nIHRoZSBjb3ZhcmlhbmNlIHBhcmFtZXRlcnMuIE1vbml0b3IgdGhlIGxpa2VsaWhvb2QgZnVuY3Rpb24gYXQgZWFjaCBzdGVwIG9mIHRoZSBhbGdvcml0aG0gdG8gY2hlY2sgY29udmVyZ2VuY2UuCgpgYGB7ciwgcGFyYW1ldGVyIGVzdGltYXRpb259CiMlJQpDX21hdHJpeCA8LSBmdW5jdGlvbih0aGV0YSl7CiAgc2lnbWEgPSB0aGV0YVsxXQogIHBoaSA9IHRoZXRhWzJdCiAgdGF1ID0gdGhldGFbM10KICBTaWdtYSA9IE1hdGVybl9jb3Yoc2lnbWEsIHBoaSwgdCkKICBDID0gRm1hdHJpeCAlKiUgU2lnbWEgJSolIHQoRm1hdHJpeCkgKyBkaWFnKE0pICogdGF1XjIKICByZXR1cm4oQykKfQoKCmRDX2RzaWdtYSA8LSBmdW5jdGlvbih0aGV0YSl7CiAgIyBzaWdtYSA9IHRoZXRhJHNpZ21hCiAgIyBwaGkgPSB0aGV0YSRwaGkKICAjIHRhdSA9IHRoZXRhJHRhdQogIHNpZ21hID0gdGhldGFbMV0KICBwaGkgPSB0aGV0YVsyXQogIHRhdSA9IHRoZXRhWzNdCiAgS20gPSBNYXRlcm5fY292KDEuMCwgcGhpLCB0KSAjIHQgaGVyZSBpcyB0aGUgZGlzdGFuY2UgbWF0cml4LCBIIGlzIHRoZSBkZXNpZ24gbWF0cml4LCBzaW1pbGFyIHRvIFgKICBkQ19kc2dtID0gRm1hdHJpeCAlKiUgS20gJSolIHQoRm1hdHJpeCkKICByZXR1cm4oZENfZHNnbSkKfQoKZENfZHBoaSA8LSBmdW5jdGlvbih0aGV0YSl7CiAgc2lnbWEgPSB0aGV0YVsxXQogIHBoaSA9IHRoZXRhWzJdCiAgdGF1ID0gdGhldGFbM10KICBLbiA9IHNpZ21hIF4gMiAqICgtcGhpICogdCkgKiBleHAoLXBoaSAqIHQpCiAgcmV0dXJuKEZtYXRyaXggJSolIEtuICUqJSB0KEZtYXRyaXgpKQp9CgpkQ19kdGF1IDwtIGZ1bmN0aW9uKHRoZXRhKXsKICByZXR1cm4oZGlhZyhNKSkKfQoKIyBVc2UgZmlzaGVyIHNjb3JpbmcgdG8gZmluZCBNTEUgcGFyYW1ldGVycwojIGJldGEgPSBucC56ZXJvcyhbMywgMV0pCmJldGEgPSBtYXRyaXgoYygtMi4xLCAzLjEsIC45KSwgbnJvdyA9IDMsIG5jb2wgPSAxKQp0aGV0YSA9IHJiaW5kKC4yNDUsIDkuMywgLjAwMykKTUFYX0lURVIgPSA1Ck5vX2l0ZXIgPSAwCmVwc2lsb24gPSAxMApCZXRhID0gbWF0cml4KDAsIG5yb3cgPSBNQVhfSVRFUiwgbmNvbCA9IDMpCkxpa2VsaWhvb2QgPSBtYXRyaXgoMCwgbnJvdyA9IE1BWF9JVEVSLCBuY29sID0gMSkKCndoaWxlIChOb19pdGVyIDwgTUFYX0lURVIgJiBlcHNpbG9uID4gLjAwMDEpewogICAgQyA9IENfbWF0cml4KHRoZXRhKQogICAgYmV0YSA9IHNvbHZlKHQoRykgJSolIHNvbHZlKEMsIEcpLCB0KEcpICUqJSBzb2x2ZShDLCB5X3NhbXBsZWQpKQogICAgIyBiZXRhID0gbnAubGluYWxnLnNvbHZlKG5wLmRvdChHLlQsIG5wLmxpbmFsZy5zb2x2ZShDLCBHKSksIG5wLmRvdChHLlQsIG5wLmxpbmFsZy5zb2x2ZShDLCB5X3NhbXBsZWQpKSkKICAgIEJldGFbTm9faXRlciwgXSA9IHQoYmV0YSkKICAgIHogPSB5X3NhbXBsZWQgLSBHICUqJSBiZXRhCiAgICBsaWsgPSAtTS8yICogbG9nKDIgKiBwaSkgLSAxLzIgKiBsb2coZGV0KEMpKSAtICAxLzIgKiB0KHopICUqJSBzb2x2ZShDLCB6KSAjIG90aGVyd2lzZSwgaXQgYmVjb21lcyBpbmYKICAgIExpa2VsaWhvb2RbTm9faXRlciwgXSA9IGxpawoKICAgICMgRmluZCBkQyovZHRoZXRhCiAgICBkQ19kU2dtID0gZENfZHNpZ21hKHRoZXRhKQogICAgZENfZFBoaSA9IGRDX2RwaGkodGhldGEpCiAgICBkQ19kVGF1ID0gZENfZHRhdSh0aGV0YSkKCiAgICB1X3NpZ21hID0gLTEvMiAqIHN1bShkaWFnKHNvbHZlKEMsIGRDX2RTZ20pKSkgKyAxLzIgKiB0KHopICUqJSBzb2x2ZShDLCBkQ19kU2dtICUqJSBzb2x2ZShDLCB6KSkKICAgIHVfZXRhID0gLTEgLyAyICogc3VtKGRpYWcoc29sdmUoQywgZENfZFBoaSkpKSArIDEgLyAyICogdCh6KSAlKiUgc29sdmUoQywgZENfZFBoaSAlKiUgc29sdmUoQywgeikpCiAgICB1X3RhdSA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIGRDX2RUYXUpKSkgKyAxIC8gMiAqIHQoeikgJSolIHNvbHZlKEMsIGRDX2RUYXUgJSolIHNvbHZlKEMsIHopKQoKICAgIHUgPSByYmluZCh1X3NpZ21hLCB1X2V0YSwgdV90YXUpCgogICAgVjExID0gLTEvMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kU2dtICUqJSBzb2x2ZShDLCBkQ19kU2dtKSkpKSkKICAgIFYxMiA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kU2dtICUqJSBzb2x2ZShDLCBkQ19kUGhpKSkpKSkKICAgIFYxMyA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kU2dtICUqJSBzb2x2ZShDLCBkQ19kVGF1KSkpKSkKICAgIFYyMSA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kUGhpICUqJSBzb2x2ZShDLCBkQ19kU2dtKSkpKSkKICAgIFYyMiA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kUGhpICUqJSBzb2x2ZShDLCBkQ19kUGhpKSkpKSkKICAgIFYyMyA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kUGhpICUqJSBzb2x2ZShDLCBkQ19kVGF1KSkpKSkKICAgIFYzMSA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kVGF1ICUqJSBzb2x2ZShDLCBkQ19kU2dtKSkpKSkKICAgIFYzMiA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kVGF1ICUqJSBzb2x2ZShDLCBkQ19kUGhpKSkpKSkKICAgIFYzMyA9IC0xIC8gMiAqIHN1bShkaWFnKHNvbHZlKEMsIChkQ19kVGF1ICUqJSBzb2x2ZShDLCBkQ19kVGF1KSkpKSkKCiAgICBWID0gbWF0cml4KGMoVjExLCBWMTIsIFYxMywgVjIxLCBWMjIsIFYyMywgVjMxLCBWMzIsIFYzMyksIG5yb3cgPSAzLCBuY29sID0gMykKICAgICMgcHJpbnQobGlrKQogICAgIyBwcmludChOb19pdGVyKQogICAgdGhldGFfbmV3ID0gdGhldGEgLSBzb2x2ZShWLCB1KSAgIyBoZXJlIGl0IGlzIG1pbnVzLCBidXQgaW4gdGhlIGJvb2ssIGl0IHNheXMgcGx1cywgbmVlZHMgdG8gYmUgcmVjaGVja2VkCiAgICBlcHNpbG9uID0gbm9ybSh0aGV0YV9uZXcgLSB0aGV0YSwgdHlwZSA9ICIyIikgLyBub3JtKGJldGEsIHR5cGUgPSAiMiIpCiAgICB0aGV0YSA9IHRoZXRhX25ldwogICAgcHJpbnQocGFzdGUoZXBzaWxvbiAsICIgLCBpdGVyIG5vIGlzICIsIE5vX2l0ZXIpKQogICAgTm9faXRlciA9IE5vX2l0ZXIgKyAxCn0KIyBwcmludChiZXRhKQojIHByaW50KEJFVEFfVFJVRSkKIyBwcmludCh0aGV0YSkKIyBwcmludChUSEVUQV9UUlVFKQoKcGxvdChjKDE6Tm9faXRlciksIExpa2VsaWhvb2QsIG1haW4gPSAibGlrZWxpaG9vZCBmdW5jdGlvbiIpCgojIGFscGhhaCA9IChzdW0obnAuYWJzKGJldGEpKSAvIDMpLnNxdWVlemUoKQp0aGV0YWggPSB0aGV0YQpzaWdtYWggPSB0aGV0YVsxXQpwaGloID0gdGhldGFbMl0KdGF1aCA9IHRoZXRhWzNdCmJldGFoID0gYmV0YQpiZXRhMSA9IGJldGFbMV0KYmV0YTIgPSBiZXRhWzJdCmJldGEzID0gYmV0YVszXQoKIyBwcmludCgnRXN0aW1hdGVkIHNpZ21hIGlzICcsIHNpZ21haCwgIlxuRXN0aW1hdGVkIGV0YSBpcyAiLCBldGFoLCBcCiMgICAgICAgIlxuRXN0aW1hdGVkIHRhdSBpcyAiLCB0YXVoLCAiXG5Fc3RpbWF0ZWQgYWxwaGEgaXMgIiwgYWxwaGFoKQpwcmludChjYXQoIlxuRXN0aW1hdGVkIHNpZ21hIGlzICIsIHJvdW5kKHNpZ21haCwgZGlnaXRzID0gMyksICI7IFRydWUgc2lnbWEgaXMgIiwgVEhFVEFfVFJVRVsxXSwgCiAgICAgICAgICAgICJcbkVzdGltYXRlZCBwaGkgaXMgIiwgcm91bmQocGhpaCwgZGlnaXRzID0gMiksICI7IFRydWUgcGhpIGlzICIsIFRIRVRBX1RSVUVbMl0sIAogICAgICAgICAgICAiXG5Fc3RpbWF0ZWQgdGF1IGlzICIsIHJvdW5kKHRhdWgsIGRpZ2l0cyA9IDUpLCAiOyBUcnVlIHRhdSBpcyAiLCBUSEVUQV9UUlVFWzNdLCAKICAgICAgICAgICAgIlxuRXN0aW1hdGVkIGJldGExIGlzICIsIHJvdW5kKGJldGExLCBkaWdpdHMgPSAyKSwgIjsgVHJ1ZSBiZXRhMSBpcyAiLCBCRVRBX1RSVUVbMV0sIAogICAgICAgICAgICAiXG5Fc3RpbWF0ZWQgYmV0YTIgaXMgIiwgcm91bmQoYmV0YTIsIGRpZ2l0cyA9IDIpLCAiOyBUcnVlIGJldGEyIGlzICIsIEJFVEFfVFJVRVsyXSwgCiAgICAgICAgICAgICJcbkVzdGltYXRlZCBiZXRhMyBpcyAiLCByb3VuZChiZXRhMywgZGlnaXRzID0gMiksICI7IFRydWUgYmV0YTMgaXMgIiwgQkVUQV9UUlVFWzNdKSkKCgpgYGAKCgoqKiogCgojIyAyLjMgS3JpZ2luZwoKV2Ugd2lsbCBub3cgdXNlIHRoZSBlc3RpbWF0ZWQgbW9kZWwgcGFyYW1ldGVycyB0byBwZXJmb3JtIGtyaWdpbmcgcHJlZGljdGlvbi4gUHJlZGljdCB2YXJpYWJsZXMgJHgocykkLCB3aGVyZSBwcmVkaWN0aW9ucyBzaXRlcyBsaWUgb24gYSByZWd1bGFyIGdyaWQgb2Ygc2l6ZSAyNXgyNSBmb3IgdGhlIHVuaXQgc3F1YXJlLiBWaXN1YWxpemUgdGhlIEtyaWdpbmcgc3VyZmFjZSBhbmQgdGhlIHByZWRpY3Rpb24gc3RhbmRhcmQgZXJyb3IuIENvbXBhcmUgd2l0aCB0aGUgdHJ1ZSBmaWVsZC4KCmBgYHtyLCBrcmlnaW5nfQpTaWdtYWggPSBNYXRlcm5fY292KHNpZ21haCwgcGhpaCwgdCkgIyBlc3RpbWF0ZWQgY292YXJpYW5jZSBtYXRyaXgKTGggPSBjaG9sKFNpZ21haCkKbWggPSBIICUqJSBiZXRhaCArIExoICUqJSBybm9ybShuKQpDaCA9IENfbWF0cml4KHRoZXRhaCkKeHAgPSBtaCArIFNpZ21haCAlKiUgdChGbWF0cml4KSAlKiUgc29sdmUoQywgKHlfc2FtcGxlZCAtIEZtYXRyaXggJSolIG1oKSkKcGxvdGYoeHAsICJwb3N0ZXJpb3IgbWVhbiIpClNpZ21hcCA9IFNpZ21haCAtIFNpZ21haCAlKiUgdChGbWF0cml4KSAlKiUgc29sdmUoQ2gsIEZtYXRyaXggJSolIFNpZ21haCkKIyBwbG90ZihTaWdtYXAsICJwb3N0ZXJpb3IgY292YXJpYW5jZSIpCmVzdGQgPSBzcXJ0KGRpYWcoU2lnbWFwKSkKcGxvdGYoZXN0ZCwgInBvc3RlcmlvciBzdGQiKQpNU0UgPSBzcXJ0KHN1bShhYnMoeHAgLSBtdV9yZWFsKSAqKiAyKSAvIG4pCnByaW50KHBhc3RlKCJUaGUgcHJlZGljdGlvbiBlcnJvciBpcyAiLCBNU0UpKQpgYGAKCioqKgoKIyBQYXJ0IElJSQoKCgoKCgoKCgoKCgo=